A contextual%2Dbandit approach to personalized news article recommendation.
Personalized web services strive to adapt their services (advertisements, news articles, etc.) to individual users by making use of both content and user information. Despite a few recent advances, this problem remains challenging for at least two reasons. First, web service is featured with dynamically changing pools of content, rendering traditional collaborative filtering methods inapplicable. Second, the scale of most web services of practical interest calls for solutions that are both fast in learning and computation. In this work, we model personalized recommendation of news articles as a contextual bandit problem, a principled approach in which a learning algorithm sequentially selects articles to serve users based on contextual information about the users and articles, while simultaneously adapting its article-selection strategy based on user-click feedback to maximize total user clicks. The contributions of this work are three-fold. First, we propose a new, general contextual bandit algorithm that is computationally efficient and well motivated from learning theory. Second, we argue that any bandit algorithm can be reliably evaluated offline using previously recorded random traffic. Finally, using this offline evaluation method, we successfully applied our new algorithm to a Yahoo! Front Page Today Module dataset containing over 33 million events. Results showed a 12.5 % click lift compared to a standard context-free bandit algorithm, and the advantage becomes even greater when data gets more scarce.
Maintaining Equilibria During Exploration in Sponsored Search Auctions.
 We introduce an exploration scheme aimed at learning advertiser click-through rates in sponsored search auctions with minimal effect on advertiser incentives. The scheme preserves both the current ranking and pricing policies of the search engine and only introduces one parameter which controls the rate of exploration. This parameter can be set so as to allow enough exploration to learn advertiser click-through rates over time, but also eliminate incentives for advertisers to alter their currently submitted bids. When advertisers have much more information than the search engine, we show that although this goal is not achievable, incentives to deviate can be made arbitrarily small by appropriately setting the exploration rate. Given that advertisers do not alter their bids, we bound revenue loss due to exploration. 
An Optimal High Probability Algorithm for the Contextual Bandit Problem

Learning from Logged Implicit Exploration Data

Learning from Logged Implicit Exploration Data



An Unbiased
We consider the problem of using a large unlabeled sample to boost performance of a learning algorithm when only a small set of labeled examples is available. In particular, we consider a setting in which the description of each example can be partitioned into two distinct views, motivated by the task of learning to classify web pages. For example, the description of a web page can be partitioned into the words occurring on that page, and the words occurring in hyperlinks that point to that page. We assume that either view of the example would be su cient for learning if we had enough labeled data, but our goal is to use both views together to allow inexpensive unlabeled data to augment amuch smaller set of labeled examples. Speci cally, the presence of two distinct views of each example suggests strategies in which two learning algorithms are trained separately on each view, and then each algorithm&#039;s predictions on new unlabeled examples are used to enlarge the training set of the other. Our goal in this paper is to provide a PAC-style analysis for this setting, and, more broadly, a PAC-style framework for the general problem of learning from both labeled and unlabeled data. We also provide empirical results on real web-page data indicating that this use of unlabeled examples can lead to signi cant improvement of hypotheses in practice. As part of our analysis, we provide new re-
Agnostic Active Learning Without Constraints

Importance Weight Aware Gradient Updates

Error%2DCorrecting Tournaments.
Abstract. We present a family of adaptive pairwise tournaments that are provably robust against large error fractions when used to determine the largest element in a set. The tournaments use nk pairwise comparisons but have only O(k + log n) depth, where n is the number of players and k is the robustness parameter (for reasonable values of n and k). These tournaments also give a reduction from multiclass to binary classification in machine learning, yielding the best known analysis for the problem. 1
Feature hashing for large scale multitask learning.
Empirical evidence suggests that hashing is an effective strategy for dimensionality reduction and practical nonparametric estimation. In this paper we provide exponential tail bounds for feature hashing and show that the interaction between random subspaces is negligible with high probability. We demonstrate the feasibility of this approach with experimental results for a new use case — multitask learning with hundreds of thousands of tasks. 1.
Tutorial summary Reductions in machine learning.

Tutorial summary Active learning.

Importance weighted active learning.
We present a practical and statistically consistent scheme for actively learning binary classifiers under general loss functions. Our algorithm uses importance weighting to correct sampling bias, and by controlling the variance, we are able to give rigorous label complexity bounds for the learning process. 1.
Learning nonlinear dynamic models.
We present a novel approach for learning nonlinear dynamic models, which leads to a new set of tools capable of solving problems that are otherwise difficult. We provide theory showing this new approach is consistent for models with long range structure, and apply the approach to motion capture and highdimensional video data, yielding results superior to standard alternatives. 1.
The offset tree for learning with partial labels.

Multi%2DLabel Prediction via Compressed Sensing
We consider multi-label prediction problems with large output spaces under the assumption of output sparsity – that the target vectors have small support. We develop a general theory for a variant of the popular ECOC (error correcting output code) scheme, based on ideas from compressed sensing for exploiting this sparsity. The method can be regarded as a simple reduction from multilabel regression problems to binary regression problems. It is shown that the number of subproblems need only be logarithmic in the total number of label values, making this approach radically more efficient than others. We also state and prove performance guarantees for this method, and test it empirically. 1.
Feature Hashing for Large Scale Multitask Learning
Empirical evidence suggests that hashing is an effective strategy for dimensionality reduction and practical nonparametric estimation. In this paper we provide exponential tail bounds for feature hashing and show that the interaction between random subspaces is negligible with high probability. We demonstrate the feasibility of this approach with experimental results for a new use case — multitask learning with hundreds of thousands of tasks. 1.
Error%2DCorrecting Tournaments
Abstract. We present a family of adaptive pairwise tournaments that are provably robust against large error fractions when used to determine the largest element in a set. The tournaments use nk pairwise comparisons but have only O(k + log n) depth, where n is the number of players and k is the robustness parameter (for reasonable values of n and k). These tournaments also give a reduction from multiclass to binary classification in machine learning, yielding the best known analysis for the problem. 1
Conditional Probability Tree Estimation Analysis and Algorithms
1.1 Main Results We consider the problem of estimating the conditional probability of a label in time O(log n), where n is the number of possible labels. We analyze a natural reduction of this problem to a set of binary regression problems organized in a tree structure, proving a regret bound that scales with the depth of the tree. Motivated by this analysis, we propose the first online algorithm which provably constructs a logarithmic depth tree on the set of labels to solve this problem. We test the algorithm empirically, showing that it works succesfully on a dataset with roughly 10 6 labels. 1
Learning Nonlinear Dynamic Models
We present a novel approach for learning nonlinear dynamic models, which leads to a new set of tools capable of solving problems that are otherwise difficult. We provide theory showing this new approach is consistent for models with long range structure, and apply the approach to motion capture and highdimensional video data, yielding results superior to standard alternatives. 1.
Search%2Dbased Structured Prediction
We describe an adaptation and application of a search-based structured prediction algorithm “Searn ” to unsupervised learning problems. We show that it is possible to reduce unsupervised learning to supervised learning and demonstrate a high-quality unsupervised shift-reduce parsing model. We additionally show a close connection between unsupervised Searn and expectation maximization. Finally, we demonstrate the efficacy of a semi-supervised extension. The key idea that enables this is an application of the predict-self idea for unsupervised learning. 1.
Provably Secure Steganography.

Agnostic active learning.
We state and analyze the first active learning algorithm which works in the presence of arbitrary forms of noise. The algorithm, A2 (for Agnostic Active), relies only upon the assumption that the samples are drawn i.i.d. from a fixed distribution. We show that A2 achieves an exponential improvement (i.e., requires only O � ln 1 ɛ samples to find an ɛ-optimal classifier) over the usual sample complexity of supervised learning, for several settings considered before in the realizable case. These include learning threshold classifiers and learning homogeneous linear separators with respect to an input distribution which is uniform over the unit sphere. 1.
Hash Kernels for Structured Data.
We propose hashing to facilitate efficient kernels. This generalizes previous work using sampling and we show a principled way to compute the kernel matrix for data streams and sparse feature spaces. Moreover, we give deviation bounds from the exact kernel matrix. This has applications to estimation on strings and graphs.
Search%2Dbased structured prediction.
We describe an adaptation and application of a search-based structured prediction algorithm “Searn ” to unsupervised learning problems. We show that it is possible to reduce unsupervised learning to supervised learning and demonstrate a high-quality unsupervised shift-reduce parsing model. We additionally show a close connection between unsupervised Searn and expectation maximization. Finally, we demonstrate the efficacy of a semi-supervised extension. The key idea that enables this is an application of the predict-self idea for unsupervised learning. 1.
Self%2Dfinanced wagering mechanisms for forecasting.
We examine a class of wagering mechanisms designed to elicit truthful predictions from a group of people without requiring any outside subsidy. We propose a number of desirable properties for wagering mechanisms, identifying one mechanism—weighted-score wagering—that satisfies all of the properties. Moreover, we show that a single-parameter generalization of weighted-score wagering is the only mechanism that satisfies these properties. We explore some variants of the core mechanism based on practical considerations. Categories and Subject Descriptors
Exploration scavenging.

Predictive Indexing for Fast Search.
We tackle the computational problem of query-conditioned search. Given a machine-learned scoring rule and a query distribution, we build a predictive index by precomputing lists of potential results sorted based on an expected score of the result over future queries. The predictive index datastructure supports an anytime algorithm for approximate retrieval of the top elements. The general approach is applicable to webpage ranking, internet advertisement, and approximate nearest neighbor search. It is particularly effective in settings where standard techniques (e.g., inverted indices) are intractable. We experimentally find substantial improvement over existing methods for internet advertisement and approximate nearest neighbors. 1
Sparse Online Learning via Truncated Gradient.
We propose a general method called truncated gradient to induce sparsity in the weights of online-learning algorithms with convex loss. This method has several essential properties. First, the degree of sparsity is continuous—a parameter controls the rate of sparsification from no sparsification to total sparsification. Second, the approach is theoretically motivated, and an instance of it can be regarded as an online counterpart of the popular L1-regularization method in the batch setting. We prove small rates of sparsification result in only small additional regret with respect to typical online-learning guarantees. Finally, the approach works well empirically. We apply it to several datasets and find for datasets with large numbers of features, substantial sparsity is discoverable. 1
Sparse Online Learning via Truncated Gradient
We propose a general method called truncated gradient to induce sparsity in the weights of online-learning algorithms with convex loss. This method has several essential properties. First, the degree of sparsity is continuous—a parameter controls the rate of sparsification from no sparsification to total sparsification. Second, the approach is theoretically motivated, and an instance of it can be regarded as an online counterpart of the popular L1-regularization method in the batch setting. We prove small rates of sparsification result in only small additional regret with respect to typical online-learning guarantees. Finally, the approach works well empirically. We apply it to several datasets and find for datasets with large numbers of features, substantial sparsity is discoverable. 1
The Offset Tree for Learning with Partial Labels

Importance Weighted Active Learning
We present a practical and statistically consistent scheme for actively learning binary classifiers under general loss functions. Our algorithm uses importance weighting to correct sampling bias, and by controlling the variance, we are able to give rigorous label complexity bounds for the learning process. 1.
Robust reductions from ranking to classification.
 We reduce ranking, as measured by the Area Under the Receiver Operating Characteristic Curve (AUC), to binary classification. The core theorem shows that a binary classification regret of r on the induced binary problem implies an AUC regret of at most 2r. This is a large improvement over approaches such as ordering according to regressed scores, which have a regret transform of r ↦ → nr where n is the number of elements.
Robust Reductions from Ranking to Classification.
 We reduce ranking, as measured by the Area Under the Receiver Operating Characteristic Curve (AUC), to binary classification. The core theorem shows that a binary classification regret of r on the induced binary problem implies an AUC regret of at most 2r. This is a large improvement over approaches such as ordering according to regressed scores, which have a regret transform of r ↦ → nr where n is the number of elements.
The Epoch%2DGreedy Algorithm for Multi%2Darmed Bandits with Side Information.

Maintaining Equilibria During Exploration in Sponsored Search Auctions.
 We introduce an exploration scheme aimed at learning advertiser click-through rates in sponsored search auctions with minimal effect on advertiser incentives. The scheme preserves both the current ranking and pricing policies of the search engine and only introduces one parameter which controls the rate of exploration. This parameter can be set so as to allow enough exploration to learn advertiser click-through rates over time, but also eliminate incentives for advertisers to alter their currently submitted bids. When advertisers have much more information than the search engine, we show that although this goal is not achievable, incentives to deviate can be made arbitrarily small by appropriately setting the exploration rate. Given that advertisers do not alter their bids, we bound revenue loss due to exploration. 
Suboptimal behavior of Bayes and MDL in classification under misspecification.
 We show that forms of Bayesian and MDL inference that are often applied to classification problems can be inconsistent. This means that there exists a learning problem such that for all amounts of data the generalization errors of the MDL classifier and the Bayes classifier relative to the Bayesian posterior both remain bounded away from the smallest achievable generalization error. From a Bayesian point of view, the result can be reinterpreted as saying that Bayesian inference can be inconsistent under misspecification, even for countably infinite models. We extensively discuss the result from both a Bayesian and an MDL perspective. 


Agnostic active learning.
We state and analyze the first active learning algorithm which works in the presence of arbitrary forms of noise. The algorithm, A2 (for Agnostic Active), relies only upon the assumption that the samples are drawn i.i.d. from a fixed distribution. We show that A2 achieves an exponential improvement (i.e., requires only O � ln 1 ɛ samples to find an ɛ-optimal classifier) over the usual sample complexity of supervised learning, for several settings considered before in the realizable case. These include learning threshold classifiers and learning homogeneous linear separators with respect to an input distribution which is uniform over the unit sphere. 1.
Outlier detection by active learning.

PAC model%2Dfree reinforcement learning.
For a Markov Decision Process with finite state (size S) and action spaces (size A per state), we propose a new algorithm—Delayed Q-Learning. We prove it is PAC, achieving near optimal performance except for Õ(SA) timesteps using O(SA) space, improving on the Õ(S2 A) bounds of best previous algorithms. This result proves efficient reinforcement learning is possible without learning a model of the MDP from experience. Learning takes place from a single continuous thread of experience—no resets nor parallel sampling is used. Beyond its smaller storage and experience requirements, Delayed Q-learning’s per-experience computation cost is much less than that of previous PAC algorithms. 1.
Cover trees for nearest neighbor.
We present a tree data structure for fast nearest neighbor operations in general npoint metric spaces (where the data set consists of n points). The data structure requires O(n) space regardless of the metric’s structure yet maintains all performance properties of a navigating net (Krauthgamer &amp; Lee, 2004b). If the point set has a bounded expansion constant c, which is a measure of the intrinsic dimensionality, as defined in (Karger &amp; Ruhl, 2002), the cover tree data structure can be constructed in O � c 6 n log n � time. Furthermore, nearest neighbor queries require time only logarithmic in n, in particular O � c 12 log n � time. Our experimental results show speedups over the brute force search varying between one and several orders of magnitude on natural machine learning datasets. 1.
Outlier detection by active learning.

Predicting Conditional Quantiles via Reduction to Classification.
We show how to reduce the process of predicting conditional quantiles (and the median in particular) to solving classification. The accompanying theoretical statement shows that the regret of the classifier bounds the regret of the quantile regression under a quantile loss. We also test this reduction empirically against existing quantile regression methods on large real-world datasets and discover that it provides state-of-theart performance. 1
E%2Dgovernment and public%2Dprivate partnerships in Canada when failure is no longer an option.

Weighted One%2DAgainst%2DAll.
3 TTI-Chicago Abstract. A reduction converts a solver for one task into a solver for another task. We introduce a notion of reduction and analyze reductions between different classification tasks. 1 Introduction There are many natural supervised learning tasks; even classification comes in a variety of different forms (binary, multiclass, cost-sensitive, importance weighted, etc.) There are two approaches that one can take: The first is to analyze all tasks independently and devise algorithms for each. The other approach is to use reductions to convert new, unexplored tasks to tasks that have been thoroughly analyzed, automatically transferring existing theory and algorithms from well-understood domains into new domains. We investigate the latter approach for classification problems. Reductions can be a powerful tool with a number of desirable properties: 1. They show how similar different tasks are. If two tasks are reducible to one
Sensitive Error Correcting Output Codes.

The Cross Validation Problem.
Cross validation allows models to be tested using the full training set by means of repeated resampling; thus, maximizing the total number of points used for testing and potentially, helping to protect against overfitting. Improvements in computational power, recent reductions in the (computational) cost of classification algorithms, and the development of closed-form solutions (for performing cross validation in certain classes of learning algorithms) makes it possible to test thousand or millions of variants of learning models on the data. Thus, it is now possible to calculate cross validation performance on a much larger number of tuned models than would have been possible otherwise. However, we empirically show how under such large number of models the risk for overfitting increases and the performance estimated by cross validation is no longer an effective estimate of generalization; hence, this paper provides an empirical reminder of the dangers of cross validation. We use a closed-form solution that makes this evaluation possible for the cross validation problem of interest. In addition, through extensive experiments we expose and discuss the effects of the overuse/misuse of cross validation in various aspects, including model selection, feature selection, and data dimensionality. This is illustrated on synthetic, benchmark, and real-world data sets. 1
A comparison of tight generalization error bounds.
We investigate the empirical applicability of several bounds (a number of which are new) on the true error rate of learned classifiers which hold whenever the examples are chosen independently at random from a fixed distribution. The collection of tricks we use includes: 1. A technique using unlabeled data for a tight derandomization of randomized bounds. 2. A tight form of the progressive validation bound. 3. The exact form of the test set bound. The bounds are implemented in the semibound package and are freely available. 1.
Relating reinforcement learning performance to classification performance.

Error limiting reductions between classification tasks.
We introduce a reduction-based model for analyzing supervised learning tasks. We use this model to devise a new reduction from multi-class cost-sensitive classification to binary classification with the following guarantee: If the learned binary classifier has error rate at most ɛ then the cost-sensitive classifier has cost at most 2ɛ times the expected sum of costs of all possible lables. Since cost-sensitive classification can embed any bounded loss finite choice supervised learning task, this result shows that any such task can be solved using a binary classification oracle. Finally, we present experimental results showing that our new reduction outperforms existing algorithms for multi-class cost-sensitive learning. 1
Covert two%2Dparty computation.
We introduce the novel concept of covert two-party computation. Whereas ordinary secure  two-party computation only guarantees that no more knowledge is leaked about the inputs of the individual  parties than the result of the computation, covert two-party computation employs steganography  to yield the following additional guarantees: (A) no outside eavesdropper can determine whether the  two parties are performing the computation or simply communicating as they normally do; (B) before  learning f(xA , xB ), neither party can tell whether the other is running the protocol; (C) after the  protocol concludes, each party can only determine if the other ran the protocol insofar as they can distinguish   f(xA , xB ) from uniformly chosen random bits. Covert two-party computation thus allows the  construction of protocols that return f(xA , xB ) only when it equals a certain value of interest (such as  &#034;Yes, we are romantically interested in each other&#034;) but for which neither party can determine whether  the other even ran the protocol whenever f(xA , xB ) does not equal the value of interest. We introduce  security definitions for covert two-party computation and we construct protocols with provable security  based on the Decisional Di#e-Hellman assumption.
Tutorial on Practical Prediction Theory for Classification.
We discuss basic prediction theory and it&#039;s impact on classification success evaluation, implications for learning algorithm design, and uses in learning algorithm execution. This tutorial is meant to be a comprehensive compilation of results which are both theoretically rigorous and practically useful. There are two important implications...
Suboptimal Behavior of Bayes and MDL in Classification Under Misspecification.
 We show that forms of Bayesian and MDL inference that are often applied to classification problems can be inconsistent. This means that there exists a learning problem such that for all amounts of data the generalization errors of the MDL classifier and the Bayes classifier relative to the Bayesian posterior both remain bounded away from the smallest achievable generalization error. From a Bayesian point of view, the result can be reinterpreted as saying that Bayesian inference can be inconsistent under misspecification, even for countably infinite models. We extensively discuss the result from both a Bayesian and an MDL perspective. 
An iterative method for multi%2Dclass cost%2Dsensitive learning.
Cost-sensitive learning addresses the issue of classification in the presence of varying costs associated with different types of misclassification. In this paper, we present a method for solving multi-class cost-sensitive learning problems using any binary classification algorithm. This algorithm is derived using three key ideas: 1) iterative weighting; 2) expanding data space; and 3) gradient boosting with stochastic ensembles. We establish some theoretical guarantees concerning the performance of this method. In particular, we show that a certain variant possesses the boosting property, given a form of weak learning assumption on the component binary classifier. We also empirically evaluate the performance of the proposed method using benchmark data sets and verify that our method generally achieves better results than representative methods for cost-sensitive learning, in terms of predictive performance (cost minimization) and, in many cases, computational efficiency.
An objective evaluation criterion for clustering.
We propose and test an objective criterion for evaluation of clustering performance: How well does a clustering algorithm run on unlabeled data aid a classification algorithm? The accuracy is quantified using the PAC-MDL bound [3] in a semisupervised setting. Clustering algorithms which naturally separate the data according to (hidden) labels with a small number of clusters perform well. A simple extension of the argument leads to an objective model selection method. Experimental results on text analysis datasets demonstrate that this approach empirically results in very competitive bounds on test set performance on natural datasets.
Suboptimal behaviour of Bayes and MDL in classification under misspecification

Telling humans and computers apart automatically.
If you try to get a new email account at Yahoo, you’ll be asked to prove that you’re a human and not a computer. Why? Because a single computer program can get thousands of free email accounts per second. And that’s bad for Yahoo. But how do you prove to a computer that you’re a human? Proving that you’re a human to another human can be done using an idea from the 1950s: the Turing Test [11]. A human judge asks you a bunch of questions and decides, depending on your answers, whether he’s talking to a human or a computer. Proving that you’re a human to a computer is another matter. It requires a test (or a set of tests) that computers can grade, humans can pass, but paradoxically, computers can’t pass. In our lingo, it requires a captcha.
Reductions Between Classification Tasks
We introduce a reduction-based model for analyzing supervised learning tasks. We use this model to devise a new reduction from multi-class cost-sensitive classification to binary classification with the following guarantee: If the learned binary classifier has error rate at most ɛ then the cost-sensitive classifier has cost at most 2ɛ times the expected sum of costs of all possible lables. Since cost-sensitive classification can embed any bounded loss finite choice supervised learning task, this result shows that any such task can be solved using a binary classification oracle. Finally, we present experimental results showing that our new reduction outperforms existing algorithms for multi-class cost-sensitive learning. 1
Computable Shell Decomposition Bounds.
Haussler, Kearns, Seung and Tishby introduced the notion of a shell decomposition of the union bound as a means of understanding certain empirical phenomena in learning curves such as phase transitions. Here we use a variant of their ideas to derive an upper bound on the generalization error of a hypothesis computable from its training error and the histogram of training errors for the hypotheses in the class. In most cases this new bound is significantly tighter than traditional bounds computed from the training error and the cardinality of the class. Our results can also be viewed as providing a rigorous foundation for a model selection algorithm proposed by Scheffer and Joachims.
Correlated equilibria in graphical games.
We examine correlated equilibria in the recently introduced formalism of graphical games, a succinct representation for multiplayer games. We establish a natural and powerful relationship between the graphical structure of a multiplayer game and a certain Markov network representing distributions over joint actions. Our first main result establishes that this Markov network succinctly represents all correlated equilibria of the graphical game up to expected payoff equivalence. Our second main result provides a general algorithm for computing correlated equilibria in a graphical game based on its associated Markov network. For a special class of graphical games that includes trees, this algorithm runs in time polynomial in the graphical game representation (which is polynomial in the number of players and exponential in the graph degree).
PAC%2DMDL Bounds.
We point out that a number of standard sample complexity  bounds (VC-dimension, PAC-Bayes, and others) are all related to the  number of bits required to communicate the labels given the unlabeled  data for a natural communication game. Motivated by this observation,  we give a general sample complexity bound based on this game that  allows us to unify these dierent bounds in one common framework.
CAPTCHA Using Hard AI Problems for Security.
We introduce captcha, an automated test that humans can  pass, but current computer programs can&#039;t pass: any program that has  high success over a captcha can be used to solve an unsolved Artificial  Intelligence (AI) problem. We provide several novel constructions of  captchas. Since captchas have many applications in practical security,  our approach introduces a new class of hard problems that can be  exploited for security purposes. Much like research in cryptography has  had a positive impact on algorithms for factoring and discrete log, we  hope that the use of hard AI problems for security purposes allows us  to advance the field of Artificial Intelligence. We introduce two families  of AI problems that can be used to construct captchas and we show  that solutions to such problems can be used for steganographic communication. captchas
Cost%2DSensitive Learning by Cost%2DProportionate Example Weighting.
We propose and evaluate a family of methods for converting classifier learning algorithms and classification theory into cost-sensitive algorithms and theory. The proposed conversion is based on cost-proportionate weighting of the training examples, which can be realized either by feeding the weights to the classification algorithm (as often done in boosting), or by careful subsampling. We give some theoretical performance guarantees on the proposed methods, as well as empirical evidence that they are practical alternatives to existing approaches. In particular, we propose  costing, a method based on cost-proportionate rejection sampling and ensemble aggregation, which achieves excellent predictive performance on two publicly available datasets, while drastically reducing the computation required by other methods.
Exploration in Metric State Spaces.
We present metric-E    , a provably near-optimal  algorithm for reinforcement learning in Markov  decision processes in which there is a natural  metric on the state space that allows the construction  of accurate local models. The algorithm is  a generalization of the E    algorithm of Kearns  and Singh, and assumes a black box for approximate  planning. Unlike the original E    , metric-    finds a near optimal policy in an amount of  time that does not directly depend on the size of  the state space, but instead depends on the covering   number of the state space. Informally, the  covering number is the number of neighborhoods  required for accurate local modeling.
Microchoice Bounds and Self Bounding Learning Algorithms.
A major topic in machine learning is to determine good upper bounds on the true error rates of learned hypotheses based upon their empirical performance on training data. In this paper, we demonstrate new adaptive bounds designed for learning algorithms that operate by making a sequence of choices. These bounds, which we call Microchoice bounds, are similar to Occam-style bounds and can be used to make learning algorithms self-bounding in the style of Freund [Fre98]. We then show how to combine these bounds with Freund&#039;s query-tree approach producing a version of Freund&#039;s query-tree structure that can be implemented with much more algorithmic efficiency.

Approximately Optimal Approximate Reinforcement Learning.
In order to solve realistic reinforcement  learning problems, it is critical  that approximate algorithms be used. In this paper,

Competitive Analysis of the Explore%2FExploit Tradeoff.
We investigate the explore/exploit trade-off in reinforcement learning using competitive analysis applied to an abstract model. We state and prove lower and upper bounds on the competitive ratio. The essential conclusion of our analysis is that optimizing the explore/exploit trade-off is much easier with a few pieces of extra knowledge such as the stopping time or upper and lower bounds on the value of the optimal exploitation policy.
PAC%2DBayes %26 Margins.
We show two related things:  (1) Given a classi  er which consists of a weighted sum of features  with a large margin, we can construct a stochastic classi  er with  negligibly larger training error rate. The stochastic classi  er has  a future error rate bound that depends on the margin distribution  and is independent of the size of the base hypothesis class.
An Improved Predictive Accuracy Bound for Averaging Classifiers.
We present an improved bound on the difference  between training and test errors for  voting classiers. This improved averaging  bound provides a theoretical justication  for popular averaging techniques such  as Bayesian classication, Maximum Entropy  discrimination, Winnow and Bayes point machines   and has implications for learning algorithm  design.  1. 
%28Not%29 Bounding the True Error.
We present a new approach to bounding the true error rate of a continuous  valued classifier based upon PAC-Bayes bounds. The method first constructs  a distribution over classifiers by determining how sensitive each  parameter in the model is to noise. The true error rate of the stochastic  classifier found with the sensitivity analysis can then be tightly bounded  using a PAC-Bayes bound. In this paper we demonstrate the method on  artificial neural networks with results of a 2 3 order of magnitude improvement  vs. the best deterministic neural net bounds.
Risk Sensitive Particle Filters.
We propose a new particle filter that incorporates a model of costs when  generating particles. The approach is motivated by the observation that  the costs of accidentally not tracking hypotheses might be significant in  some areas of state space, and next to irrelevant in others. By incorporating  a cost model into particle filtering, states that are more critical to the  system performance are more likely to be tracked. Automatic calculation  of the cost model is implemented using an MDP value function calculation  that estimates the value of tracking a particular state. Experiments in  two mobile robot domains illustrate the appropriateness of the approach.
Computable Shell Decomposition Bounds.
Haussler, Kearns, Seung and Tishby introduced the notion of a shell decomposition of the union bound as a means of understanding certain empirical phenomena in learning curves such as phase transitions. Here we use a variant of their ideas to derive an upper bound on the generalization error of a hypothesis computable from its training error and the histogram of training errors for the hypotheses in the class. In most cases this new bound is significantly tighter than traditional bounds computed from the training error and the cardinality of the class. Our results can also be viewed as providing a rigorous foundation for a model selection algorithm proposed by Scheffer and Joachims.
FeatureBoost A Meta%2DLearning Algorithm that Improves Model Robustness.
Most machine learning algorithms are lazy: they  extract from the training set the minimum information  needed to predict its labels. Unfortunately,  this often leads to models that are not robust  when features are removed or obscured in  future test data. For example, a backprop net  trained to steer a car typically learns to recognize  the edges of the road, but does not learn  to recognize other features such as the stripes  painted on the road which could be useful when  road edges disappear in tunnels or are obscured  by passing trucks. The net learns the minimum  necessary to steer on the training set. In contrast,  human driving is remarkably robust as features  become obscured. Motivated by this, we propose  a framework for robust learning that biases induction  to learn many different models from the  same inputs. We present a meta algorithm for  robust learning called FeatureBoost, and demonstrate  it on several problems using backprop nets,  k-nearest neighbor, and decision trees.
Beating the Hold%2DOut Bounds for K%2Dfold and Progressive Cross%2DValidation.
The empirical error on a test set, the hold-out estimate, often is a more reliable estimate of generalization error than the observed error on the training set, the training estimate. K-fold cross validation is used in practice with the hope of being more accurate than the hold-out estimate without reducing the number of training examples. We argue that the k-fold estimate does in fact achieve this goal. Specifically, we show that for any nontrivial learning problem and learning algorithm that is insensitive to example ordering, the k-fold estimate is strictly more accurate than a single hold-out estimate on 1/k of the data, for 2 &lt;k&lt;n(k = n is leave-one-out), based on its variance and all higher moments. Previous bounds were termed sanitycheck because they compared the k-fold estimate to the training estimate and, further, restricted the VC dimension and required a notion of hypothesis stability [2]. In order to avoid these dependencies, we consider a k-fold hypothesis that is a randomized combination or average of the k individual hypotheses. We introduce progressive validationas another possible improvement on the hold-out estimate. This estimate of the generalization error is, in many ways, as good as that of a single hold-out, but it uses an average of half as many examples for testing. The procedure also involves a hold-out set, but after an example has been tested, it is added to the training set and the learning algorithm is rerun. 1
Microchoice Bounds and Self Bounding Learning Algorithms.
A major topic in machine learning is to determine good upper bounds on the true error rates of learned hypotheses based upon their empirical performance on training data. In this paper, we demonstrate new adaptive bounds designed for learning algorithms that operate by making a sequence of choices. These bounds, which we call Microchoice bounds, are similar to Occam-style bounds and can be used to make learning algorithms self-bounding in the style of Freund [Fre98]. We then show how to combine these bounds with Freund&#039;s query-tree approach producing a version of Freund&#039;s query-tree structure that can be implemented with much more algorithmic efficiency.
Probabilistic Planning in the Graphplan Framework.
. The Graphplan planner has enjoyed considerable success as a planning algorithm for classical STRIPS domains. In this paper we explore the extent to which its representation can be used for probabilistic  planning. In particular, we consider an MDP-style framework in which the state of the world is known but actions are probabilistic, and the objective is to produce a finite horizon contingent plan with highest probability of success within the horizon. We describe two extensions of Graphplan in this direction. The first,  PGraphplan, produces an optimal contingent plan. It typically suffers a performance hit compared to Graphplan but still appears to be fast compared with other approaches to probabilistic planning problems. The second, TGraphplan, runs at essentially the same speed as Graphplan, but produces potentially sub-optimal policies: TGraphplan&#039;s policy selects the first action on the highest probability trajectory from its current state to the goal. Ideally, we would like an...
Monte Carlo Hidden Markov Models Learning Non%2DParametric Models of Partially Observable Stochastic Processes.
We present a learning algorithm for non-parametric hidden Markov models with continuous state and observation spaces. All necessary probability densities are approximated using samples, along with density trees generated from such samples. AMonte Carlo version of Baum-Welch (EM) is employed to learn models from data. Regularization during learning is achieved using an exponential shrinking technique. The shrinkage factor, which determines the effective capacity of the learning algorithm, is annealed down over multiple iterations of BaumWelch, and early stopping is applied to select the right model. Once trained, Monte Carlo HMMs can be run in an any-time fashion. We prove that under mild assumptions, Monte Carlo Hidden Markov Models converge to a local maximum in likelihood space, just like conventional HMMs. In addition, we provide empirical results obtained in a gesture recognition domain. 1 Introduction  Hidden Markov models (HMMs) [27] have been applied successfully to a large rang...
On Learning Monotone Boolean Functions.
We consider the problem of learning monotone Boolean functions over f0; 1g  n  under the uniform distribution. Specifically, given a polynomial number of uniform random samples for an unknown monotone Boolean function  f , and given polynomial computing time, we would like to approximate f as well as possible. We describe a simple algorithm that we prove achieves error at most  1=2 \Gamma \Omega\Gamma7 =  p  n), improving on the previous best bound of  1=2  \Gamma\Omega\Gamma7608  2  n)=n). We also prove that no algorithm, given a polynomial number of samples, can guarantee error  1=2 \Gamma !((log n)=  p  n), improving on the previous best hardness bound of O(1=  p  n). These lower bounds hold even if the learning algorithm is allowed membership queries. Thus this paper settles to an O(log n) factor the question of the best achievable error for learning the class of monotone Boolean functions with respect to the uniform distribution. 1. Introduction  A monotone Boolean function f maps...
